The present invention relates generally to systems for computer graphics. More specifically, the present invention includes a method and apparatus for producing accurate pixel colors using a limited number of reduced accuracy samples.
Computer systems (and related devices) typically create three-dimensional images using a sequence of stages known as a graphics pipeline. During early pipeline stages, images are modeled using a mosaic-like approach where each image is composed of a collection of individual points, lines and polygons. These points, lines and polygons are known as primitives and a single image may require thousands, or even millions, of primitives. Each primitive is defined in terms of its shape and location as well as other attributes, such as color and texture.
The primitives used in early pipeline stages are transformed, during a rasterization stage, into collections of pixels. The rasterization stage is often performed by a specialized graphics processor (in low-end systems, rasterization may be performed directly by the host processor) and the pixels are stored in a device known as a frame buffer. The frame buffer is a memory device that includes individual memory locations for each pixel.
During the rasterization stage, the graphics processor renders each primitive into the frame buffer. The graphics processor accomplishes this task by determining which pixels (i.e., which frame buffer memory locations) are included within the bounds of each primitive. The frame buffer memory locations for included pixels are then initialized to reflect the attributes of the primitive, including color and texture.
In some cases, individual pixels will include portions of more than one primitive. This may occur, for example, at the edge of overlapping or adjacent primitives. When pixels are shared between primitives, a form of pixel aliasing occurs. Pixel aliasing is generally undesirable because it is not always possible to render aliased pixels to accurately reflect each of the primitives in which they are included. As an example, consider the case of a pixel that is shared between primitives of different colors. In such a case, if the pixel is rendered to reflect the color of one primitive, it will be incorrectly colored for the remaining primitives in which it is included.
Multisample antialiasing is a technique that is designed to improve the appearance of aliased pixels. The underlying idea of multisample antialiasing is to generate color values for a series of sample locations within each pixel (rather than at a single location per-pixel). This process is generally referred to as dithering. The color values for the sample locations are generated as part of the rendering process. Each time a primitive is rendered, the color values for the samples included within that primitive are generated. When all of the primitives that include a given pixel have been rendered, a color for that pixel can be generated. The pixel color is generated by averaging, or otherwise combining the values of the color samples for that pixel.
The process of combining or averaging color sample values can be subdivided into two cases: reconstruction and construction. The first case, reconstruction, occurs when all of the color sample values have been generated for the same color value. This may happen, for example, when a pixel is included entirely within a single primitive. It can also happen when a pixel is shared between different primitives that have identical coloring at the pixel""s location. In these cases, the color sample values are optimally combined in a way that is an exact reconstruction of the original color value.
The second case, construction, occurs when the color sample values have been generated for two or more color values. This typically happens when a pixel is shared between primitives having distinct color values. In these cases, the color sample values are combined in a way that is an intermediate color value. The intermediate color value creates a visually pleasing transition between primitives.
Multisample antialiasing is an effective technique for improving the appearance of aliased pixels. At the same time, the use of multiple color samples increases the amount of memory that is used by each pixel. Memory bandwidth must also be increased to allow each of the multiple color sample values to the stored and retrieved.
Providing greater storage capacity and bandwidth makes graphics processors more expensive and makes multisample antialiasing less desirable. One way in which this disadvantage may be partially overcome is by using smaller color samples. This is the approach used within ONYX2 INFINITEREALITY computer systems produced by SILICON GRAPHICS, INC. INFINITEREALITY computer systems pair each pixel location with a series of color samples. The number of color samples used for each pixel (referred to as n in this document) is runtime configurable. Typical values for n include four, eight and sixteen color samples for each pixel. The precision of each color sample (referred to as b in this document) is based on n and the precision of each rasterized pixel (referred to as B in this document). The relation between n, b and B is defined by the equation:
b=Bxe2x88x92log2(n)
As an example, if five bits of color are stored for each rasterized pixel (i.e., B=5) and four color samples are used for each pixel (n=4), then each color sample would have a precision of three bits (b=3). The rasterizing process generates the n color sample values for each pixel using a set of equations of the form:
S[k]=MIN(2bxe2x88x921,(c+k)/n)
where c is the color value being sampled and k ranges from 0 to nxe2x88x921 and where division is performed as integer division with no remainder. For the preceding example of n=4 and b=3, the following equations are used:
S[0]=MIN(7,(c)/4)
S[1]=MIN(7,(c+1)/4)
S[2]=MIN(7,(c+2)/4)
S[3]=MIN(7,(c+3)/4)
The color sample values S[k] are then combined to form a pixel color value r using the equation:
r=S[0]+S[1]+S[2]+. . . S[nxe2x88x921]
The INFINITEREALITY multisample antialiasing method is an effective method for reducing the number of bits that must be stored for each color sample. Unfortunately, the INFINITEREALITY multisample antialiasing method does not accurately reconstruct all color values. This occurs because each color sample has limited precision. As the color value being sampled is increased, the value that must be stored in each color sample also increases. There is a point where increasing the color value being sampled would cause the values of the color samples to overflow their limited precision. This overflow is prevented because each color sample value is limited, or clamped, to a predefined maximum value of 2nxe2x88x921. The color sample values generated for the numerically greatest nxe2x88x921 color values may include one or more of these clamped values. Thus, in the example case of n=4 and b=3, the numerically greatest color is 31. The color sample values generated for the values 31, 30, and 29 each include one or more clamped values and, as a result, are not correctly reconstructed.
This result is summarized in the following table:
The inability to reconstruct nxe2x88x921 possible color values is, of course, not a crippling limitation. Still, there is no doubt that this is a disadvantage of this multisample antialiasing method.
Based on the preceding, it may be appreciated that a need exists for multisampling antialiasing methods that make effective use of smaller color samples. To be effective, techniques of this type should provide accurate reconstruction of all color values using smaller color samples. Effective techniques should also maximize the range of reproducible colors. It is also important for techniques of this type to be practical, both in terms of structural complexity and cost to produce.
An embodiment of the present invention includes a method and apparatus for multisample dithering. For a representative embodiment of this method, the graphics pipeline uses a series of color samples for each pixel. The number of color samples used for each pixel (referred to as n) is preferably configurable and generally ranges from four to sixteen color samples per-pixel. The precision of each color sample (referred to as b) is defined by the equation:
b=Bxe2x88x92log2(n)
where B is the precision of each rasterized pixel.
The b bits of each color sample do not directly correspond to the values 0 to 2bxe2x88x921. Instead, each color sample (except the first) is defined to span the somewhat larger range of 0 to 2b. This is accomplished by defining an omitted value for each color sample (except the first). The bit patterns of the omitted values are used to represent the value 2b (inclusive). This means that each color sample can represent all but one of the values between 0 and 2b. As an example, a color sample having three bits would normally span the range of values zero to seven. The present invention would use the same three bits to span the range of values zero to eight. The bit patterns of the omitted values for these color samples would be used to represent the value eight.
The process of converting color values to color sample values is configured so that omitted values are not generated. This is done by mapping each color value to a predefined series of color sample values. In cases where the series of color sample values defined for a color value would normally include an omitted value, the offending color sample value is defined to be the omitted value minus one and the defined value of the color sample value that precedes it in the series is incremented by one to compensate.
Color sample values 2b cannot be directly stored. Instead, each value of this type is replaced with the bit pattern of its associated omitted value. The process of replacing 2b with the bit patterns of omitted values is reversed when color sample values are retrieved.
The color sample values for a pixel are combined by summation. The summation is performed in a way that treats the bit patterns of omitted values as the value 2b. Using this method, all of the color values between 0 and 2Bxe2x88x921 are accurately reconstructed without increasing the precision required for individual color samples. At the same time, the color sample values are guaranteed to be relatively close to exact values. This means that constructed colors are close to their correct values. Each color sample value is also formed independently. This prevents the types of failure that may occur when heuristics are used to define color sample values based on the values of other color samples. The same method may also be used to further reduce the precision required for each color sample while still maintaining the accuracy of traditional dithering methods.
Advantages of the invention will be set forth, in part, in the description that follows and, in part, will be understood by those skilled in the art from the description herein. The advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims and equivalents.